home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxunfa.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  6KB  |  270 lines
  1. /* classes: src_files */
  2.  
  3. /*    Copyright (C) 1995, 1996 Tom Lord
  4.  * 
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU Library General Public License as published by
  7.  * the Free Software Foundation; either version 2, or (at your option)
  8.  * any later version.
  9.  * 
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU Library General Public License for more details.
  14.  * 
  15.  * You should have received a copy of the GNU Library General Public License
  16.  * along with this software; see the file COPYING.  If not, write to
  17.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  18.  * Boston, MA 02111-1307, USA. 
  19.  */
  20.  
  21.  
  22.  
  23. #include "rxall.h"
  24. #include "rx.h"
  25. #include "rxunfa.h"
  26. #include "rxnfa.h"
  27.  
  28.  
  29. #ifdef __STDC__
  30. static int
  31. unfa_equal (void * va, void * vb)
  32. #else
  33. static int
  34. unfa_equal (va, vb)
  35.      void * va;
  36.      void * vb;
  37. #endif
  38. {
  39.   return rx_rexp_equal ((struct rexp_node *)va, (struct rexp_node *)vb);
  40. }
  41.  
  42.  
  43. struct rx_hash_rules unfa_rules = { unfa_equal, 0, 0, 0, 0 };
  44.  
  45.  
  46. #ifdef __STDC__
  47. static struct rx_cached_rexp *
  48. canonical_unfa (struct rx_hash * table, struct rexp_node * rexp, int cset_size)
  49. #else
  50. static struct rx_cached_rexp *
  51. canonical_unfa (table, rexp, cset_size)
  52.      struct rx_hash * table;
  53.      struct rexp_node * rexp;
  54.      int cset_size;
  55. #endif
  56. {
  57.   struct rx_hash_item * it;
  58.   it = rx_hash_store (table, rx_rexp_hash (rexp, 0), rexp, &unfa_rules);
  59.  
  60.   if (it->binding == 0)
  61.     {
  62.       struct rx_cached_rexp * cr;
  63.  
  64.       if (it->data == (void *)rexp)
  65.     rx_save_rexp (rexp);
  66.       
  67.       cr = (struct rx_cached_rexp *)malloc (sizeof (*cr));
  68.       rx_bzero ((char *)cr, sizeof (*cr));
  69.       if (!cr)
  70.     return 0;
  71.       it->binding = (void *)cr;
  72.       cr->unfa.nfa = 0;
  73.       cr->unfa.exp = rexp;
  74.       cr->hash_item = it;
  75.       rx_save_rexp (rexp);
  76.     }
  77.   return (struct rx_cached_rexp *)it->binding;
  78. }
  79.  
  80.  
  81. #ifdef __STDC__
  82. static struct rx *
  83. rx_unfa_rx (struct rx_cached_rexp * cr, struct rexp_node * exp, int cset_size)
  84. #else
  85. static struct rx *
  86. rx_unfa_rx (cr, exp, cset_size)
  87.      struct rx_cached_rexp * cr;
  88.      struct rexp_node * exp;
  89.      int cset_size;
  90. #endif
  91. {
  92.   struct rx * new_rx;
  93.  
  94.   if (cr->unfa.nfa)
  95.     return cr->unfa.nfa;
  96.  
  97.   new_rx = rx_make_rx (cset_size);
  98.   if (!new_rx)
  99.     return 0;
  100.   {
  101.     struct rx_nfa_state * start;
  102.     struct rx_nfa_state * end;
  103.     start = end = 0;
  104.     if (!rx_build_nfa (new_rx, exp, &start, &end))
  105.       {
  106.     free (new_rx);
  107.     return 0;
  108.       }
  109.     new_rx->start_nfa_states = start;
  110.     end->is_final = 1;
  111.     start->is_start = 1;
  112.     {
  113.       struct rx_nfa_state * s;
  114.       int x;
  115.       x = 0;
  116.       for (s = new_rx->nfa_states; s; s = s->next)
  117.     s->id = x++;
  118.     }
  119.   }
  120.   cr->unfa.nfa = new_rx;
  121.   return new_rx;
  122. }
  123.  
  124.  
  125.  
  126.  
  127. #ifdef __STDC__
  128. struct rx_unfaniverse *
  129. rx_make_unfaniverse (int delay)
  130. #else
  131. struct rx_unfaniverse *
  132. rx_make_unfaniverse (delay)
  133.      int delay;
  134. #endif
  135. {
  136.   struct rx_unfaniverse * it;
  137.   it = (struct rx_unfaniverse *)malloc (sizeof (*it));
  138.   if (!it) return 0;
  139.   rx_bzero ((char *)it, sizeof (*it));
  140.   it->delay = delay;
  141.   return it;
  142. }
  143.  
  144.  
  145. #ifdef __STDC__
  146. void
  147. rx_free_unfaniverse (struct rx_unfaniverse * it)
  148. #else
  149. void
  150. rx_free_unfaniverse (it)
  151.      struct rx_unfaniverse * it;
  152. #endif
  153. {
  154. }
  155.  
  156.  
  157.  
  158.  
  159.  
  160. #ifdef __STDC__
  161. struct rx_unfa *
  162. rx_unfa (struct rx_unfaniverse * unfaniverse, struct rexp_node * exp, int cset_size)
  163. #else
  164. struct rx_unfa *
  165. rx_unfa (unfaniverse, exp, cset_size)
  166.      struct rx_unfaniverse * unfaniverse;
  167.      struct rexp_node * exp;
  168.      int cset_size;
  169. #endif
  170. {
  171.   struct rx_cached_rexp * cr;
  172.   if (exp && exp->cr)
  173.     cr = exp->cr;
  174.   else
  175.     {
  176.       cr = canonical_unfa (&unfaniverse->table, exp, cset_size);
  177.       if (exp)
  178.     exp->cr = cr;
  179.     }
  180.   if (!cr)
  181.     return 0;
  182.   if (cr->next)
  183.     {
  184.       if (unfaniverse->free_queue == cr)
  185.     {
  186.       unfaniverse->free_queue = cr->next;
  187.       if (unfaniverse->free_queue == cr)
  188.         unfaniverse->free_queue = 0;
  189.     }
  190.       cr->next->prev = cr->prev;
  191.       cr->prev->next = cr->next;
  192.       cr->next = 0;
  193.       cr->prev = 0;
  194.       --unfaniverse->delayed;
  195.     }
  196.   ++cr->unfa.refs;
  197.   cr->unfa.cset_size = cset_size;
  198.   cr->unfa.verse = unfaniverse;
  199.   rx_unfa_rx (cr, exp, cset_size);
  200.   return &cr->unfa;
  201. }
  202.  
  203.  
  204. #ifdef __STDC__
  205. void
  206. rx_free_unfa (struct rx_unfa * unfa)
  207. #else
  208. void
  209. rx_free_unfa (unfa)
  210.      struct rx_unfa * unfa;
  211. #endif
  212. {
  213.   struct rx_cached_rexp * cr;
  214.   cr = (struct rx_cached_rexp *)unfa;
  215.   if (!cr)
  216.     return;
  217.   if (!--cr->unfa.refs)
  218.     {
  219.       if (!unfa->verse->free_queue)
  220.     {
  221.       unfa->verse->free_queue = cr;
  222.       cr->next = cr->prev = cr;
  223.     }
  224.       else
  225.     {
  226.       cr->next = unfa->verse->free_queue;
  227.       cr->prev = unfa->verse->free_queue->prev;
  228.       cr->next->prev = cr;
  229.       cr->prev->next = cr;
  230.     }
  231.  
  232.       ++unfa->verse->delayed;
  233.       while (unfa->verse->delayed > unfa->verse->delay)
  234.     {
  235.       struct rx_cached_rexp * it;
  236.       it = unfa->verse->free_queue;
  237.       unfa->verse->free_queue = it->next;
  238.       if (!--unfa->verse->delayed)
  239.         unfa->verse->free_queue = 0;
  240.       it->prev->next = it->next;
  241.       it->next->prev = it->prev;
  242.       if (it->unfa.exp)
  243.         it->unfa.exp->cr = 0;
  244.       rx_free_rexp ((struct rexp_node *)it->hash_item->data);
  245.       rx_hash_free (it->hash_item, &unfa_rules);
  246.       rx_free_rx (it->unfa.nfa);
  247.       rx_free_rexp (it->unfa.exp);
  248.       free (it);
  249.       if (it == cr)
  250.         break;
  251.     }
  252.     }
  253.   else
  254.     return;
  255. }
  256.  
  257.  
  258. #ifdef __STDC__
  259. void
  260. rx_save_unfa (struct rx_unfa * unfa)
  261. #else
  262. void
  263. rx_save_unfa (unfa)
  264.      struct rx_unfa * unfa;
  265. #endif
  266. {
  267.   ++(unfa->refs);
  268. }
  269.  
  270.